package com.lx.algorithm.code.xly3.class03;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-04 18:31:26
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-04     张李鑫                     1.0         1.0 Version
 */
public class Code04 {
    /**
     * 请注意区分子串和子序列的不同，给定两个字符串str1和str2，
     * 求两个字符的最长公共子序列
     * <p>
     * 动态规划的空间压缩技巧！
     */

    public static int lcSubsequence(String str, String str1) {
        if (str == null || str1 == null) {
            return 0;
        }

        return process(str.toCharArray(), str1.toCharArray(), 0, 0);
    }

    /**
     * 普通递归
     *
     * @param str
     * @param str1
     * @param i
     * @param l
     * @return
     */
    private static int process(char[] str, char[] str1, int i, int l) {
        if (i == str.length || l == str1.length) {
            return 0;
        }
        int p4 = process(str, str1, i + 1, l + 1);
//        int p1 = 0;
        if (str[i] == str1[l]) {

            p4+=1;
        }
        int p2 = process(str, str1, i + 1, l);
        int p3 = process(str, str1, i, l + 1);


        return Math.max(p2, Math.max(p3, p4));
    }

    public static int dp(String str, String str1) {
        if (str == null || str1 == null) {
            return 0;
        }
        char[] s1 = str.toCharArray();
        char[] s2 = str1.toCharArray();
        int[][] dp = new int[s1.length + 1][s2.length + 1];

        int max = 0;
        int N = s1.length;
        int M = s2.length;
        for (int i = N - 1; i >= 0; i--) {
            for (int j = M - 1; j >= 0; j--) {
                int p1 = dp[i + 1][j + 1];
                int p2 = dp[i + 1][j];
                int p3 = dp[i][j + 1];
                if (s1[i] == s2[j]) {
                    p1 += 1;
                }
                dp[i][j] = Math.max(Math.max(p1, p2), p3);
                max = Math.max(dp[i][j], max);
            }
        }
        return max;

    }


    public static void main(String[] args) {
        String str1="asdfg";
        String str2="asdfgg";
        System.out.println(lcSubsequence(str1, str2));
        System.out.println(dp(str1, str2));
    }

}
